#include<stdio.h>

int bag01(int n, int *w, int *v, int c, int (*m)[11])
{//n是物品个数,w是重量数组,v是价值数组,c是背包最大容量,
 //m[i][j]表示存前i个物品，背包是j重量下的最大值
	for (int i = 0; i <= n; i++)
	{
		m[0][i] = 0;
	}
	for (int i = 0; i <= n; i++)
	{
		m[i][0] = 0;
	}

	//int vmax = 0;
	for (int i = 1; i <= n; i++)
	{//物品个数重量重量

		for (int j = 1; j <= c; j++)
		{//背包重量
			if (w[i] <= j)
			{
				int temp = m[i-1][j-w[i]] + v[i];

				if (temp > m[i-1][j])
					m[i][j] = temp;
				else
					m[i][j] = m[i-1][j];
			}
			else
				m[i][j] = m[i-1][j];
		}
	}
}

void traceback(int n, int *w, int c, int (*m)[11], int *x)
{
	for(int i = n; i>1; i--)
	{
		if(m[i][c] == m[i-1][c])
			x[i] = 0;
		else
		{
			x[i] = 1;
			c = c - w[i];
		}

		x[1] = (m[1][c])?1:0;
	}
}


void Knapsack(int *w,int *v,int c,int n,int m[][100],int s[][100])
{//v是硬币的重量,w是硬币的价值,c是总付款,n是硬币个数
 //m[i][j]表示只允许使用前i种硬币,总付款为j时所使用的零钱最轻重量
 //递归式为：m[i][j] = min{m[i-1][j], m[i][j-w[i]]+v[i]}
 //m[i-1][j]表示如果使用第i枚硬币的价值是大于总价值则不使用第i枚硬币
 //m[i][j-w[i]]+v[i]表示使用了一次i硬币,两者的较小值为该问题规模下的解
	int j,q,i;
	for(q=1;q<=c;q++) 
	{//给定的硬币第一个硬币必须是价值为1的保证因为总价值除以硬币价值除不尽的情况，即保证不存在无解的情况
		m[1][q]=q*v[1];
		s[1][q]=1;
	}

	for(i=2;i<=n;i++)
	{
		for(j=1;j<=c;j++)//问题规模为m[i][j]的情况下
		{
			m[i][j]=m[i-1][j];
			s[i][j]=s[i-1][j];
			if(j-w[i]>=0&&m[i][j-w[i]]+v[i]<=m[i-1][j])
			{
				m[i][j]=m[i][j-w[i]]+v[i];
				//m[i][j]=m[i][j-v[i]]+w[i];
				s[i][j]=i;
			}
		}
	}

}

int main()
{	
	int w[]={0,1,2,4,6};//硬币的价值
	int n=4;
	int c=12;
	int i,j;
	int v[]={0,1,4,6,8};//硬币的重量
	int m[100][100]={0};
	int s[100][100]={0};
	Knapsack(v,w,c,n,m,s);
	for(j=1;j<=4;j++)
	{
		for(i=1;i<=12;i++)
		printf("%d ",m[j][i]);
		printf("\n");
	}
	printf("ss\n");
	for(j=1;j<=4;j++)
	{
		for(i=1;i<=12;i++)
			printf("%d ",s[j][i]);
		printf("\n");
	}
	printf("11");
}

/*
int main(void)
{
	
	int m[6][13] = {{0}};
	int v[6] = {0, 2, 5, 3, 10, 4};
	int w[6] = {0, 1, 3, 2, 6, 2};
	int c =12;
	
	int m[6][11] = {{0}};
	int v[6] = {0,6, 3, 5, 4, 6};
	int w[6] = {0,2, 2, 6, 5, 4};
	int c =10;

	int x[6] = {0};
	bag01(5, w, v, c, m);
	traceback(5, w, c, m, x);

	printf("%d\n", m[5][10]);

	for(int i = 1; i<=5; i++)
	{
		printf("%d\n", x[i]);
	}
}
*/